package com.ljy.my_study.leetcode.打砖块;

/**
 * @author lijunying
 * @date 2021/1/18 8:22
 */
public class TestMain {

//    有一个 m x n 的二元网格，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
//
//    一块砖直接连接到网格的顶部，或者
//    至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
//    给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，
//    然后其他的砖块可能因为这一消除操作而掉落。一旦砖块掉落，它会立即从网格中消失（即，它不会落在其他稳定的砖块上）。
//
//    返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
//
//    注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
//
//             
//    示例 1：
//
//    输入：grid = [[1,0,0,0],[1,1,1,0]], hits = [[1,0]]
//    输出：[2]
//    解释：
//    网格开始为：
//            [[1,0,0,0]，
//            [1,1,1,0]]
//    消除 (1,0) 处加粗的砖块，得到网格：
//            [[1,0,0,0]
//            [0,1,1,0]]
//    两个加粗的砖不再稳定，因为它们不再与顶部相连，也不再与另一个稳定的砖相邻，因此它们将掉落。得到网格：
//            [[1,0,0,0],
//            [0,0,0,0]]
//    因此，结果为 [2] 。
//    示例 2：
//
//    输入：grid = [[1,0,0,0],[1,1,0,0]], hits = [[1,1],[1,0]]
//    输出：[0,0]
//    解释：
//    网格开始为：
//            [[1,0,0,0],
//            [1,1,0,0]]
//    消除 (1,1) 处加粗的砖块，得到网格：
//            [[1,0,0,0],
//            [1,0,0,0]]
//    剩下的砖都很稳定，所以不会掉落。网格保持不变：
//            [[1,0,0,0],
//            [1,0,0,0]]
//    接下来消除 (1,0) 处加粗的砖块，得到网格：
//            [[1,0,0,0],
//            [0,0,0,0]]
//    剩下的砖块仍然是稳定的，所以不会有砖块掉落。
//    因此，结果为 [0,0] 。
//
//    提示：
//
//    m == grid.length
//    n == grid[i].length
//1 <= m, n <= 200
//    grid[i][j] 为 0 或 1
//            1 <= hits.length <= 4 * 104
//    hits[i].length == 2
//            0 <= xi <= m - 1
//            0 <= yi <= n - 1
//    所有 (xi, yi) 互不相同
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/bricks-falling-when-hit
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        System.out.println(2<<(11));
    }

    public int[] hitBricks(int[][] grid, int[][] hits) {
        int rows=grid.length;
        int cols=grid[0].length;
        int[][] copy=new int[rows][cols];
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                copy[i][j]=grid[i][j];
            }
        }
        for(int i=0;i<hits.length;i++){
            copy[hits[i][0]][hits[i][1]]=0;
        }
        int size=rows*cols;
        UnionFind unionFind=new UnionFind(size+1);
        for(int i=0;i<cols;i++){
            if(copy[0][i]==1){
                unionFind.connect(i,size);
            }
        }
        for(int i=1;i<rows;i++){
            for(int j=0;j<cols;j++){
                if(copy[i][j]==1){
                    if(copy[i-1][j]==1){
                        unionFind.connect(getIndex(i-1,j,cols),getIndex(i,j,cols));
                    }
                    if(inRange(i,j-1,rows,cols)&&copy[i][j-1]==1){
                        unionFind.connect(getIndex(i,j-1,cols),getIndex(i,j,cols));
                    }
                }
            }
        }

        int[] result=new int[hits.length];

        int[][] directions={{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
        for(int i=hits.length-1;i>=0;i--){
            int[] hit=hits[i];
            int x=hit[0];
            int y=hit[1];

            if(grid[x][y]==0){
                continue;
            }
            int count=unionFind.getParentSize(size);
            if(x==0){
                unionFind.connect(y,size);
            }

            for(int j=0;j<directions.length;j++){
                int newX=x+directions[j][0];
                int newY=y+directions[j][1];
                if(inRange(newX,newY,rows,cols)&&copy[newX][newY]==1){
                    unionFind.connect(getIndex(x,y,cols),getIndex(newX,newY,cols));
                }
            }
            int newCount=unionFind.getParentSize(size);
            result[i]=newCount-count;
            // 减去的 1 是逆向补回的砖块（正向移除的砖块），与 0 比较大小，是因为存在一种情况，添加当前砖块，不会使得与屋顶连接的砖块数更多
            result[i] = Math.max(0, newCount - count - 1);
            copy[x][y]=1;
        }

        return result;
    }

    private int getIndex(int x,int y,int cols){
        return x*cols+y;
    }

    private boolean inRange(int x,int y,int rows,int cols){
        return x>=0&&x<rows&&y>=0&&y<cols;
    }

    private class UnionFind{
        private int n;
        private int[] id;
        private int[] size;

        public UnionFind(int n){
            this.n=n;
            this.id=new int[n];
            this.size=new int[n];
            for(int i=0;i<n;i++){
                this.id[i]=i;
                this.size[i]=1;
            }
        }

        public int find(int num){
            if(num!=id[num]){
                id[num]=find(id[num]);
            }
            return id[num];
        }

        public boolean connect(int x,int y){
            int xId=find(x);
            int yId=find(y);
            if(xId==yId){
                return false;
            }
             if(size[xId]<size[yId]){
                 int tmp=yId;
                 yId=xId;
                 xId=tmp;
             }
            id[xId]=yId;
            size[yId]+=size[xId];
            return true;
        }

        public int getParentSize(int num){
            return size[find(num)];
        }
    }
}
